Modern computers typically take advantage of the concept of pipelining when processing instructions. The instruction pipeline in a computer will have a plurality of stages, with each stage being able to operate on one instruction at the same time while a different stage is operating on another instruction. It is desirable to keep the pipeline full so that each stage in the pipeline is processing an instruction, in order to utilize the pipeline to its maximum effectiveness. To keep the pipeline full, the pipeline often must make certain predictions, such as which sequence of instructions to follow after a conditional branch instruction. If the prediction is correct, the execution of the instructions can follow without incident. However, if the wrong path of instructions is followed after the conditional branch instruction, then the pipeline must be backed up to the conditional branch instruction and the instructions of the correct path input to the pipeline for execution.
One of the problems that arises with the backing up of the pipeline is the fact that the values of the registers used in the execution of instructions will have changed between the time the conditional branch instruction was performed and when the error condition is recognized, as explained more fully below.
In modern computers, registers are used to store values. A typical instruction processed by the pipeline will add the values stored in two different registers and place the resulting value in a third register. For example, an instruction may be "add R7, R8.fwdarw.R9". This means that the contents of registers R7 and R8 should be added together and the result placed in register R9.
A problem results when a subsequent instruction calls for the use of a register that was changed since an earlier instruction passed through the pipeline. For example, assume that the instruction immediately following the instruction "add R7, R8.fwdarw.R9" is the instruction "add R1, R2.fwdarw.R7". In executing the second instruction, the contents of register R7 have been changed. If the first instruction, in which the contents of registers R7 and R8 are added, were to be performed over again after execution of the second instruction, due to a back up of the pipeline, the resulting value to be stored in R9 would be different.
In a pipelined computer, in which, for example, twenty instructions can be processed through the pipeline before a missed prediction or other trap condition is recognized, the value contained in any one of the registers may have been changed many times. There is therefore a need to save the results generated at certain pipeline stages until the complete pipeline has run its course, in case an event occurs that requires the pipeline to back up to a previous known state.
One approach for saving the results is register renaming. In register renaming, there are a number of registers, for example, thirty-two, which can be used by the instructions executed by the pipeline. These registers are hereinafter referred to as "logical registers". With register renaming, each logical register is mapped into a physical home located in a pool of registers that is larger than the number of logical registers. Each result generated for a logical register is given a new physical home in the pool of registers. Typically, the pool of registers is kept in a register file. Thus, multiple generations of the same logical register will be available and held in different physical homes in the register file.
In order to implement a register renaming scheme, a mechanism must be provided to determine what physical home holds the latest value for each logical register. This mechanism may be called a register map. In addition, it must be possible to restore the state of the register map to a state it was in at some time in the past, in order to be able to effectively back the pipeline up to that time in the past and process instructions again from that state.